// // 【变式例题】设有一组初始记录关键字序列（K1，K2，…，Kn），
// // 要求设计一个算法能够在 O(n)的时间复杂度内将线性表划分成两部分，
// // 其中左半部分的每个关键字均小于 Ki，右半部分的每个关键字均大于等于 Ki。
//
// #include <stdio.h>
// #include <stdlib.h>
// #include <windows.h>
//
// typedef struct SqList {
//     int* data;
//     int length;
//     int maxsize;
// } SqList;
//
// void InitSq(SqList* L) {
//     L->data = NULL;
//     L->length = 0;
//     L->maxsize = 0;
// }
//
// void DestroySq(SqList* L) {
//     free(L->data);
//     L->data = NULL;
//     L->length = L->maxsize = 0;
// }
//
// void FullSq(SqList* L) {
//     if (L->length == L->maxsize) {
//         int newcapacity = (L->maxsize == 0 ? 4 : 2 * L->maxsize);
//         int* tmp = (int*)realloc(L->data, sizeof(int) * newcapacity);
//         if (tmp == NULL) {
//             exit(1);
//         }
//         L->data = tmp;
//         L->maxsize = newcapacity;
//     }
// }
//
// void InsertBack(SqList* L, int e) {
//     FullSq(L);
//     L->data[L->length] = e;
//     L->length++;
// }
//
// void Partition(SqList* L, int ki) {
//     int left = 0;
//     int right = L->length - 1;
//
//     while (left <= right) {
//         // 找到第一个大于等于 ki 的元素
//         while (left <= right && L->data[left] < ki) {
//             left++;
//         }
//
//         // 找到第一个小于 ki 的元素
//         while (left <= right && L->data[right] >= ki) {
//             right--;
//         }
//
//         // 交换这两个元素
//         if (left < right) {
//             int temp = L->data[left];
//             L->data[left] = L->data[right];
//             L->data[right] = temp;
//         }
//     }
// }
//
//
// int main() {
//     SetConsoleOutputCP(CP_UTF8);
//     SqList list;
//     InitSq(&list);
//
//     // 添加测试数据
//     InsertBack(&list, 2);
//     InsertBack(&list, 3);
//     InsertBack(&list, 5);
//     InsertBack(&list, -2);
//     InsertBack(&list, -9);
//     InsertBack(&list, 7);
//     InsertBack(&list, 0);
//     InsertBack(&list, -3);
//     InsertBack(&list, 11);
//     InsertBack(&list, -5);
//     InsertBack(&list, -3);
//
//     printf("排序前: ");
//     for (int i = 0; i < list.length; i++) {
//         printf("%d ", list.data[i]);
//     }
//
//     // 基于-1进行划分
//     Partition(&list, -1);
//
//     printf("\n排序后: ");
//     for (int i = 0; i < list.length; i++) {
//         printf("%d ", list.data[i]);
//     }
//
//     DestroySq(&list);
//     return 0;
// }
